﻿#include "SeqList.h"

void initList(SeqList& L)
{
	L.data = (DataType*)malloc(initSize * sizeof(DataType));
	if (!L.data)
	{
		printf("存储分配错误\n");
		exit(1);
	}
	L.maxSize = initSize;
	L.n = 0;
}

void clearList(SeqList& L)
{
	L.n = 0;
}

int Length(SeqList& L)
{
	return L.n;
}

bool isEmpty(SeqList& L)
{
	return L.n == 0;
}

bool isFull(SeqList& L)
{
	return L.n == L.maxSize;
}

bool createList(SeqList& L, DataType A[], int n)
{
	L.data = (DataType*)malloc(initSize * sizeof(DataType));
	if (!L.data)
	{
		return false;
	}
	for (int i = 0; i < n; i++)
	{
		L.data[i] = A[i];
	}
	L.maxSize = initSize;
	L.n = n;
	return true;
}

int Search(SeqList& L, DataType x)
{
	for (int i = 0; i < L.n; i++)
	{
		if (L.data[i] == x)
		{
			return i;
		}
	}
	return -1;
}

int Locate(SeqList& L, int i)
{
	if (i > 0 && i <= L.n)
	{
		return i - 1;
	}
	return -1;
}

bool Insert(SeqList& L, int i, DataType& x)
{
	if (L.n == L.maxSize)
	{
		return false;
	}
	if (i <= 0 || i > L.n + 1)
	{
		return false;
	}
	for (int j = L.n - 1; j >= i - 1; j--)
	{
		L.data[j + 1] = L.data[j];
	}
	L.data[i - 1] = x;
	L.n++;
	return true;
}

bool Remove(SeqList& L, int i, DataType& x)
{
	if (!L.n)
	{
		return false;
	}
	if (i <= 0 || i > L.n)
	{
		return false;
	}
	x = L.data[i - 1];
	for (int j = i; j < L.n; j++)
	{
		L.data[j - 1] = L.data[j];
	}
	L.n--;
	return true;
}

void printList(SeqList& L)
{
	for (int i = 0; i < L.n; i++)
	{
		printf("%d\n", L.data[i]);
	}
}

void Merge(SeqList& L1, SeqList& L2)
{
	DataType x;
	int n = Length(L1);
	int m = Length(L2);
	int k;
	for (int i = 0; i < m; i++)
	{
		x = L2.data[i];
		k = Search(L1, x);
		if (k == -1)
		{
			Insert(L1, n, x);
			n++;
		}
	}
}

void Intersection(SeqList& L1, SeqList& L2)
{
	int n = Length(L1);
	int m = Length(L2);
	int i = 1;
	int k;
	DataType x;
	while (i <= n)
	{
		x = L1.data[i];
		k = Search(L2, x);
		if (k == -1)
		{
			Remove(L1, i, x);
			n--;
		}
		else
		{
			i++;
		}
	}
}

//int main() {
//	SeqList L;
//	DataType x;
//	int pos;
//
//	// 1. 初始化顺序表
//	initList(L);
//	printf("顺序表初始化成功，当前长度: %d\n", Length(L));
//
//	// 2. 插入元素
//	printf("\n插入元素 10, 20, 30:\n");
//	x = 10; Insert(L, 1, x);
//	x = 20; Insert(L, 2, x);
//	x = 30; Insert(L, 3, x);
//	printList(L);  // 打印: 10 20 30
//
//	// 3. 查找元素
//	printf("\n查找元素 20:\n");
//	pos = Search(L, 20);
//	if (pos != -1) printf("找到元素 20，位置: %d\n", pos + 1);
//	else printf("未找到元素 20\n");
//
//	// 4. 删除元素
//	printf("\n删除第 2 个元素:\n");
//	if (Remove(L, 2, x)) {
//		printf("删除成功，删除的元素: %d\n", x);
//		printList(L);  // 打印: 10 30
//	}
//	else {
//		printf("删除失败\n");
//	}
//
//	// 5. 检查空/满状态
//	printf("\n检查顺序表状态:\n");
//	printf("是否为空? %s\n", isEmpty(L) ? "是" : "否");
//	printf("是否为满? %s\n", isFull(L) ? "是" : "否");
//
//	// 6. 清空顺序表
//	printf("\n清空顺序表:\n");
//	clearList(L);
//	printf("清空后长度: %d\n", Length(L));  // 打印: 0
//
//	// 7. 通过数组创建顺序表
//	printf("\n通过数组创建顺序表:\n");
//	DataType A[] = { 5, 15, 25 };
//	int n = sizeof(A) / sizeof(A[0]);
//	if (createList(L, A, n)) {
//		printf("创建成功:\n");
//		printList(L);  // 打印: 5 15 25
//	}
//	else {
//		printf("创建失败\n");
//	}
//
//	SeqList L1, L2;
//	L1 = L;
//	L2 = L;
//	DataType y;
//	y = 40; Insert(L1, 4, y);
//	y = 50; Insert(L1, 5, y);
//	y = 60; Insert(L1, 6, y);
//	y = 60; Insert(L2, 4, y);
//	y = 70; Insert(L2, 5, y);
//	y = 80; Insert(L2, 6, y);
//	y = 90; Insert(L2, 7, y);
//	printf("-------------------\n");
//	Merge(L1, L2);
//	printList(L1);
//	Intersection(L1, L2);
//	printList(L1);
//	return 0;
//}